#include <stdio.h>
#include <stdlib.h>  
#include <math.h>
#include "projet.h"
#include "parser.h"
#include "algo1.h"
#include "cycle3.h"
#include "cycle4.h"
#include "cycle5.h"
#include "optimisation.h"


int main(int argc,char** argv){

  char lignes[NB_LIGNES_MAX][TAILLE_LIGNES_MAX];
  int nb_terminaux = remplir_lignes(lignes,argv[1]);
  int i;
  int **distances=malloc(nb_terminaux*sizeof(int*));
  for(i=0;i<nb_terminaux;i++)
    distances[i] = malloc(nb_terminaux * sizeof(int));

  int **liens=malloc(nb_terminaux*sizeof(int*));
  for(i=0;i<nb_terminaux;i++)
    liens[i] = malloc(nb_terminaux * sizeof(int));

  creer_graphe(liens,distances,nb_terminaux,lignes);


  int a=0;
  while(a!=1&&a!=2){
    printf("\nQuelle algo ?\n1er algo: 1\nKruskal: 2\n");
    scanf("%d",&a);
  }
  if(a==1)
    creer_liens1(liens,distances,nb_terminaux);
  if(a==2)
    kruskal(liens,distances,nb_terminaux);

  
  int k;
  k = choisir_k(liens,distances,nb_terminaux);

  if(k==3)
    creation_des_cycles_3(liens,distances,nb_terminaux);
  if(k==4)
    creation_des_cycles_4(liens,distances,nb_terminaux);
  if(k==5)
    creation_des_cycles_5(liens,distances,nb_terminaux);

  liens_inutile(distances,liens,nb_terminaux,k);


  if(k==3&&(est_connexe(liens,distances,nb_terminaux)==1)&&(verifie_cycle_3(liens,nb_terminaux)==1))
    printf("Graphe solution");
  if(k==4&&est_connexe(liens,distances,nb_terminaux)==1&&verifie_cycle_4(liens,nb_terminaux)==1)
    printf("Graphe solution");
  if(k==5&&est_connexe(liens,distances,nb_terminaux)==1&&verifie_cycle_5(liens,nb_terminaux)==1)
    printf("Graphe solution");

  int l;
  l = longueur_cable(liens,distances,nb_terminaux);
  printf("\nLongueur de cable: %d\n",l);
  

  transcrireDot(liens,distances,nb_terminaux);
  

  for(i=0;i<nb_terminaux;i++){
    free(distances[i]);
    free(liens[i]);
  }
  free(liens);
  free(distances);
}

/**
Fonction qui affiche les distances d'un terminal s a tous les autres terminaux.
**/
void afficher_distance_s(int** liens,int** distances,int nb_terminaux,int s){
    int t;
    int d[nb_terminaux];
    int pere[nb_terminaux];   
    dijkstra(liens,distances,nb_terminaux,s,d,pere);
    for(t=0;t<nb_terminaux;t++)
      printf(" %d ",d[t]);
}

/**
Fonction qui affiche une matrice.
**/
void afficher(int **m,int n){
  int i;
  int j;
  for(i=0;i<n;i++){
    printf("\n");
    for(j=0;j<n;j++)
      printf("   %d   ",m[i][j]);
  }
  printf("\n");
}


/**
Fonction qui test si un graphe est connexe.
**/
int est_connexe(int** liens,int** distances,int nb_terminaux){
  int i;
  int j;
  int d[nb_terminaux];
  int pere[nb_terminaux]; 
  for(i=0;i<nb_terminaux;i++){  
    dijkstra(liens,distances,nb_terminaux,i,d,pere);
    for(j=0;j<nb_terminaux;j++)
      if(d[j]==-1)
	return 0;
  }
  return 1;
}

/**
Fonction qui calcul la longueur de cable utilisée pour relier les terminaux.
**/
int longueur_cable(int** liens,int** distances,int nb_terminaux){
  int c = 0;
  int i;
  int j;
  for(i=0;i<nb_terminaux;i++)
    for(j=0;j<nb_terminaux;j++)
      if(j>i&&liens[i][j]==1)
	c = c + distances[i][j];
  return c;
}

int choisir_k(int** liens,int** distances,int nb_terminaux){
  int k=0;
  while(k!=3&&k!=4&&k!=5){
    printf("\nQuelle valeur de k ?");
    scanf("%d",&k);
  }
  return k;
}

void kruskal(int** liens,int** distances,int nb_terminaux){
  int n;
  n = (nb_terminaux)*(nb_terminaux);
  int* trie_liens;
  trie_liens = malloc(n*sizeof(int));
  trier(distances,trie_liens,nb_terminaux);

  int i;
  int j;
  int* partitions;
  partitions = malloc(nb_terminaux*sizeof(int));
  for(i=0;i<nb_terminaux;i++)
    partitions[i]  = i;

  int k;
  int p;
  for(k=0;k<n;k++){
    i = trie_liens[k]/nb_terminaux;
    j = trie_liens[k]%nb_terminaux;
    if(partitions[i]!=partitions[j]){
      liens[i][j] = 1;
      liens[j][i] = 1;
      for(p=0;p<nb_terminaux;p++)
	if((p!=j)&&(partitions[p] == partitions[j]))
	  partitions[p] = partitions[i];
      partitions[j] = partitions[i];
    }
  }

  free(trie_liens);
  free(partitions);
}



void trier(int** distances,int* trie_liens,int nb_terminaux){
  int i;
  int j;
  int n;
  n = (nb_terminaux)*(nb_terminaux);

  int* ordre;
  ordre = malloc(n*sizeof(int));
  for(i=0;i<nb_terminaux;i++)
    for(j=0;j<nb_terminaux;j++)
      ordre[i*nb_terminaux + j] = distances[i][j];

  int* trie;
  trie = malloc(n*sizeof(int));
  for(i=0;i<nb_terminaux;i++)
    for(j=0;j<nb_terminaux;j++)
      trie[i*nb_terminaux + j] = distances[i][j];

  int min;
  int imin;
  for(i=0;i<n;i++){
    min = -1;
    for(j=i;j<n;j++)
      if((min==-1)||(trie[j]<min)){
	min = trie[j];
	imin = j;
      }
    for(j=imin;j>i;j--)
      trie[j] = trie[j-1];
    trie[i] = min;
  }

  int* t;
  t = malloc(n*sizeof(int));
  for(i=0;i<n;i++)
    t[i]  = 1;

  int x;
  for(i=0;i<n;i++){
    x = trie[i];
    j=0;
    while((ordre[j]!=x||t[j]==0)&&j<n)
      j++;
    trie_liens[i] = j;
    t[j] = 0;
  }

  free(trie); 
  free(t);
  free(ordre);
}


